This invention is in the field of integrated circuits for data communication, and is more specifically directed to error correction methods in the receipt of such communications.
Recent advances in the electronics field have now made high-speed digital data communications prevalent in many types of applications and uses. Digital communication techniques are now used for communication of audio signals for telephony, with video telephony now becoming available in some locations. Digital communication among computers is also prevalent, particularly with the advent of the Internet; of course, computer-to-computer networking by way of dedicated connections (e.g., local-area networks) and also by way of dial-up connections has also become prevalent in recent years.
Of course, the quality of communications carried out in these ways depends upon the accuracy with which the received signals match the transmitted signals. Some types of communications, such as audio communications, can withstand bit loss to a relatively large degree. However, the communication of digital data, especially of executable programs, requires exact fidelity in order to be at all useful. Accordingly, various techniques for the detection and correction of errors in communicated digital bit streams have been developed. Indeed, error correction techniques have effectively enabled digital communications to be carried out over available communication facilities, such as existing telephone lines, despite the error rates inherent in high-frequency communication over these facilities.
Error correction may also be used in applications other than the communication of data and other signals over networks. For example, the retrieval of stored data by a computer from its own magnetic storage devices also typically utilizes error correction techniques to ensure exact fidelity of the retrieved data; such fidelity is, of course, essential in the reliable operation of the computer system from executable program code stored in its mass storage devices. Digital entertainment equipment, such as compact disc players, digital audio tape recorders and players, and the like also now typically utilize error correction techniques to provide high fidelity output.
An important class of error detection and error correction techniques is referred to as Reed-Solomon coding, and was originally described in Reed and Solomon, "Polynomial Codes over Certain Finite Fields", J. Soc. for Industrial and Applied Mathematics, Vol. 8 (SIAM, 1960), pp. 300-304. Reed-Solomon coding uses finite-field arithmetic, such as Galois field arithmetic, to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block. Considering a message as made up of k m-bit elements, a polynomial of degree n-1 may be determined as having n coefficients; with n greater than k (i.e., the polynomial is overspecified), not all of the n coefficients need be valid in order to fully and accurately recover the message. According to Reed-Solomon coding, the number t of errors that may be corrected is determined by the relationship between n and k, according to ##EQU1## Reed-Solomon encoding is used to generate the encoded message in such a manner that, upon decoding of the received encoded message, the number and location of any errors in the received message may be determined. Conventional Reed-Solomon encoder and decoder functions are generally implemented, in microprocessor-based architectures, as dedicated hardware units that are not in the datapath of the central processing unit (CPU) of the system, as CPU functionality has not heretofore been extended to include these functions.
In this regard, FIG. 1 illustrates one example of an architecture for a conventional Reed-Solomon encoder, for the example where each symbol is eight bits, or one byte, in size (i.e., m=8), where Galois field arithmetic is used such that the size of the Galois field is 2.sup.8, and where the maximum codeword length is 2.sup.8 -1, or 255 symbols. Of course, other architectures may be used to derive the encoded codeword for the same message and checksum parameters, or of course for other symbol sizes, checksum lengths, or maximum codeword lengths. In the example of FIG. 1, sixteen check symbols are generated for each codeword, and as such eight errors per codeword may be corrected. According to conventional Reed-Solomon encoding, the k message bytes in the codeword (M.sub.k-1, M.sub.k-2, . . . ,M.sub.0) are used to generate the check symbols (C.sub.15, C.sub.14, . . . , C.sub.0). The check symbols C are the coefficients of a polynomial C(x) EQU C(x)=C.sub.13 x.sup.15 +C.sub.14 x.sup.14 + . . . +C.sub.0
which is the remainder of the division of a message polynomial M(x) having the message bytes as coefficients: EQU M(x)=M.sub.k-1 x.sup.k-1 +M.sub.k-2 x.sup.k-2 + . . . +M.sub.0
by a divisor referred to as generator polynomial G(x): EQU G(x)=(x-a.sup.0)(x-a.sup.1)(x-a.sup.2) . . . (x-a.sup.15)
where each value is a root of the binary primitive polynomial x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1. The exemplary architecture of FIG. 1 includes sixteen eight-bit shift register latches 6.sub.15 through 6.sub.0, which will contain the remainder values from the polynomial division, and thus will present the checksum coefficients C.sub.15 through C.sub.0, respectively. An eight-bit exclusive-OR function 8.sub.15 through 8.sub.1 is provided between each pair of shift register latches 6 to effect Galois field addition, with XOR function 8.sub.15 located between latches 6.sub.15 and 6.sub.14, and so on. The feedback path produced by exclusive-OR function 2, which receives both the input symbol and the output of the last latch 6.sub.15, presents the quotient for each division step. This quotient is broadcast to sixteen constant Galois field multipliers 4.sub.15 through 4.sub.0 , which multiply the quotient by respective ones of the coefficients G.sub.15 through G.sub.0. In operation, the first k symbols contain the message itself, and are output directly as the leading portion of the codeword. Each of these message symbols enters the encoder architecture of FIG. 1 on lines IN, and is applied to the division operation carried out by this encoder. Upon completion of the operations of the architecture of FIG. 1 upon these message bytes, the remainder values retained in shift register latches 6.sub.15 through 6.sub.0 correspond to the checksum symbols C.sub.15 through C.sub.0, and are appended to the encoded codeword after the k message symbols.
The encoded codewords are then communicated in a digital bitstream, and communicated in the desired manner, after the appropriate formatting. For communications over telephone facilities, of course, the codewords may be communicated either digitally or converted to analog signals; digital network or intracomputer communications will, of course, maintain the codewords in their digital format. Regardless of the communications medium, errors may occur in the communicated signals, and will be reflected in the received bitstream as opposite binary states from those in the input bitstream, prior to the encoding process of FIG. 1. These errors are sought to be corrected in the decoding process, as will now be described in a general manner relative to FIG. 2.
An example of the decoding of Reed-Solomon encoded codewords, generated for example by the architecture of FIG. 1, is conventionally carried out in the manner now to be described relative to decoder 10 illustrated in FIG. 2. Decoder 10 receives an input bitstream of codeword symbols, which is considered, for a single codeword, as received polynomial r(x) in FIG. 2. Received polynomial r(x) is applied to syndrome accumulator 12, which generates a syndrome polynomial s(x) of the form: EQU s(x)=s.sub.i-1 x.sup.i-1 +s.sub.i-2 x.sup.i-2 + . . . +s.sub.1 x+s.sub.0
Syndrome polynomial s(x) is indicative of whether errors were introduced into the communicated signals over the communication facility. If s(x)=0, no errors were present, but if s(x) is non-zero, one or more errors are present in the codeword under analysis. Syndrome polynomial s(x), in the form of a sequence of coefficients, is then forwarded to Euclidean array function 15.
Euclidean array function 15 generates two polynomials .LAMBDA.(x) and .OMEGA.(x) based upon the syndrome polynomial s(x) received from syndrome accumulator 12. The degree v of error locator polynomial .LAMBDA.(x) indicates the number of errors in the codeword, and as such is forwarded to Chien search function 16 for additional analysis. Polynomial .OMEGA.(x) is also generated by Euclidean array function 15, and is forwarded to Forney function 18 for use in evaluation of the error in the received bitstream r(x).
As noted above, the coefficients of the error locator polynomial .LAMBDA.(x) generated by Euclidean array function 15 are applied to Chien search function 16 in this conventional Reed-Solomon decoder. Chien search function 16 utilizes these coefficients, along with the particular finite field "alphabet", or set of finite field values, to generate a polynomial, generally referred to as zeroes polynomial X(x), that is used in further identifying the errors in the received bitstream r(x). Zeroes polynomial X(x) is applied to Forney function 18 for determination of the eventual error magnitude polynomial M(x). Chien search function 16 also forwards zeroes polynomial X(x) to error position circuit 17 which generates error position polynomial P(x) therefrom. Error magnitude polynomial M(x) and error position polynomial P(x) are forwarded to input ring buffer 19 as an indication of the magnitude and position, respectively, of the errored symbols in the bitstream r(x). Input ring buffer 19 then generates the output bitstream i'(x) by effectively subtracting the designated error magnitude from the identified position of the error, so that output bitstream i'(x) faithfully represents input bitstream r(x).
Referring now to FIG. 3, an example of the construction and operation of a conventional custom logic implementation of error position circuit 17 will now be described in detail. As shown in FIG. 3, data words corresponding to terms of zeroes polynomial X(x) are received by multiplexer 20 of error position circuit 17; in this example of Galois field (204, 188, 8 ) Reed-Solomon decoding, zeroes polynomial includes, in this example, eight-bit terms X(0) through X(t), where t is the number of correctable errors. Of course, the higher-order terms of zeroes polynomial X(x) will be zero if the number of detected roots is less than its maximum. The output of multiplexer 20 forwards the selected one of the terms of zeroes polynomial X(x) to Galois field divide circuit 28, the quotient of which is then forwarded to Galois field logarithm circuit 29. Accordingly, error position circuit 17 generates a term P(i) of the error position polynomial P(x) by performing the following operations upon a corresponding term X(i) of zeroes polynomial X(x): EQU P(i)=GF.sub.-- log [GF.sub.-- div(1,X(i)]
Accordingly, error position term P(i) is derived as the logarithm of the reciprocal of the value of the corresponding zeroes term X(i).
Multiplexer 20 is controlled responsive to a count generated by adder 22 and register 24. According to this conventional example, adder 22 receives a unity input at one input, and the output of register 24 at its other input; the output of adder 22 is applied to the input of register 24. As such, adder 22 increments the contents of register 24 each machine cycle, advancing the count accordingly. In this conventional circuit, after all of the values of zeroes polynomial X(x) have been generated by Chien search function 16, adder 22 and register 24 count from zero to the number t of correctable errors; the output of register 24 is applied to a control input of multiplexer 20, such that multiplexer 20 forwards the term X(i) to Galois field divide circuit 28 responsive to receiving the count value i from register 24 at its control input. The output of register 24 is also applied to decoder 26, which decodes the count into t enable signals EN(0) through EN(t) that control the operation of corresponding ones of registers 30.sub.0 through 30.sub.t as will now be described.
The output of Galois field logarithm circuit 29 is applied to the data input of each of registers 30.sub.0 through 30.sub.t. The outputs of registers 30.sub.0 through 30.sub.t present terms P(0) through P(t), respectively, of error position polynomial P(x) to input ring buffer 19 (FIG. 2). Each of registers 30.sub.0 through 30.sub.t is enabled by its corresponding one of enable signals EN(0) through EN(t), such that the output of Galois field logarithm circuit 29 is stored by only the one of registers 30.sub.0 through 30.sub.t corresponding to the current value of the count presented to multiplexer 20 by register 24. This operation, of course, ensures that the logarithm of the reciprocal of the selected term of zeroes polynomial X(x) is stored in the corresponding one of registers 30.sub.0 through 30.sub.t.
According to conventional techniques, Galois field divide circuit 28 and Galois field logarithm circuit 29 are each implemented by way of look-up tables, generally realized as read-only-memories (ROMs). The look-up table entries of Galois field divide circuit 28 include the Galois field reciprocal of their respective addresses, thus effecting the reciprocal operation. Similarly, the look-up table entries of Galois field logarithm circuit 29 store the Galois field natural logarithm of their respective addresses. The number of equivalent gates consumed by Galois field divide circuit 28 and Galois field logarithm circuit 29 is quite substantial, according to conventional realizations. According to one exemplary technology, 630.75 gates are required to realize Galois field divide circuit 28, and 631 gates are required to realize Galois field logarithm circuit 29. As a result, the realization of error position circuit 17, excluding error position registers 30, consumes 1367.25 equivalent gates. The implementation of error position circuit 17 in custom logic circuitry thus involves significant chip area.